/******************************************************************************
*  A Teaching GA       Developed by Hal Stringer & Annie Wu, UCF
*  Version 2, January 18, 2004
*******************************************************************************/

import java.io.*;
import java.util.*;
import java.text.*;

public class Search {

/*******************************************************************************
*                           INSTANCE VARIABLES                                 *
*******************************************************************************/

/*******************************************************************************
*                           STATIC VARIABLES                                   *
*******************************************************************************/

 public static FitnessFunction problem;

 public static Chromo[] member;
 public static Chromo[] child;

 public static Chromo bestOfGenChromo;
 public static int bestOfGenR;
 public static int bestOfGenG;
 public static Chromo bestOfRunChromo;
 public static int bestOfRunR;
 public static int bestOfRunG;
 public static Chromo bestOverAllChromo;
 public static int bestOverAllR;
 public static int bestOverAllG;

 public static double sumRawFitness;
 public static double sumRawFitness2; // sum of squares of fitness
 public static double sumSclFitness;
 public static double sumProFitness;
 public static double defaultBest;
 public static double defaultWorst;

 public static double averageRawFitness;
 public static double stdevRawFitness;

 public static int G;
 public static int R;
 public static Random r = new Random();
 private static double randnum;

 private static int memberIndex[];
 private static double memberFitness[];
 private static int TmemberIndex;
 private static double TmemberFitness;

 private static double fitnessStats[][];  // 0=Avg, 1=Best

/*******************************************************************************
*                              CONSTRUCTORS                                    *
*******************************************************************************/


/*******************************************************************************
*                             MEMBER METHODS                                   *
*******************************************************************************/


/*******************************************************************************
*                             STATIC METHODS                                   *
*******************************************************************************/

   public static double[][] readDataPoints() throws java.io.IOException{
      System.out.println(Parameters.dataInputFileName);
      Scanner input = new Scanner(new FileInputStream(Parameters.dataInputFileName));
      int numPoints = input.nextInt();
      double [][] dataPoints = new double[numPoints][2];
      int i = 0;
      while (input.hasNextDouble())
      {
         dataPoints[i][0] = input.nextDouble();
         dataPoints[i++][1] = input.nextDouble();
      }
      input.close();
      return dataPoints;
   }

 public static void main(String[] args) throws java.io.IOException{

  Calendar dateAndTime = Calendar.getInstance(); 
  Date startTime = dateAndTime.getTime();

    // Read Parameter File
  System.out.println("\nParameter File Name is: " + args[0] + "\n");
  Parameters parmValues = new Parameters(args[0]);

    // Write Parameters To Summary Output File
  String summaryFileName = Parameters.expID + "_summary.txt";
  FileWriter summaryOutput = new FileWriter(summaryFileName);
  parmValues.outputParameters(summaryOutput);
      
      // Create a csv writer for handling average best fitness
      CSVDataWriter avgBestFitnessWriter = new
         CSVDataWriter(Parameters.generations, "avgBestFitness.csv");

      // Create a csv writer for handling average average fitness
      CSVDataWriter avgAvgFitnessWriter = new 
         CSVDataWriter(Parameters.generations, "avgAvgFitness.csv");

      // Create a csv writer for finding the best end stats
      CSVDataWriter endBestStatsWriter = new
         CSVDataWriter(1, "endBestStats.csv");
      
      // Create a stats writer for the first optimum found
      CSVDataWriter firstOptimumStatsWriter = new
         CSVDataWriter(1, "firstOptimumStats.csv");

    // Set up Fitness Statistics matrix
  fitnessStats = new double[2][Parameters.generations];
  for (int i=0; i<Parameters.generations; i++){
   fitnessStats[0][i] = 0;
   fitnessStats[1][i] = 0;
  }

 // Problem Specific Setup - For new new fitness function problems, create
 // the appropriate class file (extending FitnessFunction.java) and add
 // an else_if block below to instantiate the problem.
 
  int representation = 0;
      if (Parameters.problemType.equals("NM")){
    problem = new NumberMatch();
  }
  else if (Parameters.problemType.equals("OM")){
    problem = new OneMax();
  }
  else if (Parameters.problemType.equals("KM"))
  {
    problem = new KeaneFitnessFunction();
    representation = 3;
  }
  /*
      else if (Parameters.problemType.equals("BN")){
            problem = new CurveFittingFitnessFunction(readDataPoints());
            representation = 1;
      }
      else if (Parameters.problemType.equals("GC")){
            problem = new CurveFittingFitnessFunction(readDataPoints());
            representation = 2;
      }
      else if (Parameters.problemType.equals("FP")){
         problem = new FloatingPointCurveFitting(readDataPoints());
         representation = 3;
      }
      else if (Parameters.problemType.equals("AD")){
         problem = new Coefficients(readDataPoints());   
         representation = 4;
      }*/
      else System.out.println("Invalid Problem Type");

  System.out.println(problem.name);

 // Initialize RNG, array sizes and other objects
  r.setSeed(Parameters.seed);
  memberIndex = new int[Parameters.popSize];
  memberFitness = new double[Parameters.popSize];
  member = new Chromo[Parameters.popSize];
  child = new Chromo[Parameters.popSize];
  bestOfGenChromo = Chromo.createType(representation);
  bestOfRunChromo = Chromo.createType(representation);
  bestOverAllChromo = Chromo.createType(representation);

  if (Parameters.minORmax.equals("max")){
   defaultBest = 0;
   defaultWorst = 999999999999999999999.0;
  }
  else{
   defaultBest = 999999999999999999999.0;
   defaultWorst = 0;
  }

  bestOverAllChromo.rawFitness = defaultBest;

  //  Start program for multiple runs
  for (R = 1; R <= Parameters.numRuns; R++){

   bestOfRunChromo.rawFitness = defaultBest;
   System.out.println();

   // Initialize First Generation
   for (int i=0; i<Parameters.popSize; i++){
    member[i] = Chromo.createType(representation);
    child[i] = Chromo.createType(representation); 
   }
   
  //for (int i = 0; i < Parameters.popSize; i++)
    // System.out.println(member[i]);

         // Save the higher than the possible generation that the best optimum was found
         int firstOptimalGeneration = Parameters.generations;

   // Begin Each Run
   for (G=0; G<Parameters.generations; G++){

    sumProFitness = 0;
    sumSclFitness = 0;
    sumRawFitness = 0;
    sumRawFitness2 = 0;
    bestOfGenChromo.rawFitness = defaultBest;

    // Test Fitness of Each Member
    for (int i=0; i<Parameters.popSize; i++){

     member[i].rawFitness = 0;
     member[i].sclFitness = 0;
     member[i].proFitness = 0;

     problem.doRawFitness(member[i]);

     sumRawFitness = sumRawFitness + member[i].rawFitness;
     sumRawFitness2 = sumRawFitness2 +
      member[i].rawFitness * member[i].rawFitness;

     if (Parameters.minORmax.equals("max")){
      if (member[i].rawFitness > bestOfGenChromo.rawFitness){
       Chromo.copyB2A(bestOfGenChromo, member[i]);
       bestOfGenR = R;
       bestOfGenG = G;
      }
      if (member[i].rawFitness > bestOfRunChromo.rawFitness){
       Chromo.copyB2A(bestOfRunChromo, member[i]);
       bestOfRunR = R;
       bestOfRunG = G;
      }
      if (member[i].rawFitness > bestOverAllChromo.rawFitness){
       Chromo.copyB2A(bestOverAllChromo, member[i]);
       bestOverAllR = R;
       bestOverAllG = G;
      }
     }
     else {
      if (member[i].rawFitness < bestOfGenChromo.rawFitness){
       Chromo.copyB2A(bestOfGenChromo, member[i]);
       bestOfGenR = R;
       bestOfGenG = G;
      }
      if (member[i].rawFitness < bestOfRunChromo.rawFitness){
       Chromo.copyB2A(bestOfRunChromo, member[i]);
       bestOfRunR = R;
       bestOfRunG = G;
      }
      if (member[i].rawFitness < bestOverAllChromo.rawFitness){
       Chromo.copyB2A(bestOverAllChromo, member[i]);
       bestOverAllR = R;
       bestOverAllG = G;
      }
     }
    }

    // Accumulate fitness statistics
    fitnessStats[0][G] += sumRawFitness / Parameters.popSize;
    fitnessStats[1][G] += bestOfGenChromo.rawFitness;

    averageRawFitness = sumRawFitness / Parameters.popSize;
    stdevRawFitness = Math.sqrt(
       Math.abs(sumRawFitness2 - 
       sumRawFitness*sumRawFitness/Parameters.popSize)
       /
       (Parameters.popSize-1)
       );

    // Output generation statistics to screen
    System.out.println(R + "\t" + G +  "\t" + bestOfGenChromo.rawFitness + "\t" + averageRawFitness + "\t" + stdevRawFitness);

    // Output generation statistics to summary file
    summaryOutput.write(" R ");
    Hwrite.right(R, 3, summaryOutput);
    summaryOutput.write(" G ");
    Hwrite.right(G, 3, summaryOutput);
    summaryOutput.write("  " + bestOfGenChromo.rawFitness);
    //Hwrite.right((int)bestOfGenChromo.rawFitness, 7, summaryOutput);
    summaryOutput.write("   " + averageRawFitness);
    //Hwrite.right(averageRawFitness, 11, 3, summaryOutput);
    summaryOutput.write("  " + stdevRawFitness);
    //Hwrite.right(stdevRawFitness, 11, 3, summaryOutput);
    summaryOutput.write("\n");

            // Save the earliest optimum found for our stats writer
            // Lets assume that 100 is the max fitness always (change later)
            if (((int)bestOfGenChromo.rawFitness) == 100)
               firstOptimalGeneration = Math.min(G,firstOptimalGeneration);

            // Add the data we collected to our private csv files
            // so that way we can read them in excel and make charts!
            avgBestFitnessWriter.addDatum(G, bestOfGenChromo.rawFitness);
            avgAvgFitnessWriter.addDatum(G, averageRawFitness);

  // *********************************************************************
  // **************** SCALE FITNESS OF EACH MEMBER AND SUM ***************
  // *********************************************************************

    switch(Parameters.scaleType){

    case 0:     // No change to raw fitness
     for (int i=0; i<Parameters.popSize; i++){
      member[i].sclFitness = member[i].rawFitness + .000001;
      sumSclFitness += member[i].sclFitness;
     }
     break;

    case 1:     // Fitness not scaled.  Only inverted.
     for (int i=0; i<Parameters.popSize; i++){
      member[i].sclFitness = 1/(member[i].rawFitness + .000001);
      sumSclFitness += member[i].sclFitness;
     }
     break;

    case 2:     // Fitness scaled by Rank (Maximizing fitness)

     //  Copy genetic data to temp array
     for (int i=0; i<Parameters.popSize; i++){
      memberIndex[i] = i;
      memberFitness[i] = member[i].rawFitness;
     }
     //  Bubble Sort the array by floating point number
     for (int i=Parameters.popSize-1; i>0; i--){
      for (int j=0; j<i; j++){
       if (memberFitness[j] > memberFitness[j+1]){
        TmemberIndex = memberIndex[j];
        TmemberFitness = memberFitness[j];
        memberIndex[j] = memberIndex[j+1];
        memberFitness[j] = memberFitness[j+1];
        memberIndex[j+1] = TmemberIndex;
        memberFitness[j+1] = TmemberFitness;
       }
      }
     }
     //  Copy ordered array to scale fitness fields
     for (int i=0; i<Parameters.popSize; i++){
      member[memberIndex[i]].sclFitness = i;
      sumSclFitness += member[memberIndex[i]].sclFitness;
     }

     break;

    case 3:     // Fitness scaled by Rank (minimizing fitness)

     //  Copy genetic data to temp array
     for (int i=0; i<Parameters.popSize; i++){
      memberIndex[i] = i;
      memberFitness[i] = member[i].rawFitness;
     }
     //  Bubble Sort the array by floating point number
     for (int i=1; i<Parameters.popSize; i++){
      for (int j=(Parameters.popSize - 1); j>=i; j--){
       if (memberFitness[j-i] < memberFitness[j]){
        TmemberIndex = memberIndex[j-1];
        TmemberFitness = memberFitness[j-1];
        memberIndex[j-1] = memberIndex[j];
        memberFitness[j-1] = memberFitness[j];
        memberIndex[j] = TmemberIndex;
        memberFitness[j] = TmemberFitness;
       }
      }
     }
     //  Copy array order to scale fitness fields
     for (int i=0; i<Parameters.popSize; i++){
      member[memberIndex[i]].sclFitness = i;
      sumSclFitness += member[memberIndex[i]].sclFitness;
     }

     break;

    default:
     System.out.println("ERROR - No scaling method selected");
    }


  // *********************************************************************
  // ****** PROPORTIONALIZE SCALED FITNESS FOR EACH MEMBER AND SUM *******
  // *********************************************************************

    for (int i=0; i<Parameters.popSize; i++){
     member[i].proFitness = member[i].sclFitness/sumSclFitness;
     sumProFitness = sumProFitness + member[i].proFitness;
    }

  // *********************************************************************
  // ************ CROSSOVER AND CREATE NEXT GENERATION *******************
  // *********************************************************************
    //   old crossover mechanism
    //    
 //    int parent1 = -1;
 //    int parent2 = -1;
 //
 //    //  Assumes always two offspring per mating
 //    for (int i=0; i<Parameters.popSize; i=i+2){
 //
 //     // Select Two Parents
 //     parent1 = Chromo.selectParent();
 //     parent2 = parent1;
 //     while (parent2 == parent1){
 //      parent2 = Chromo.selectParent();
 //     }
 //
 //     // Crossover Two Parents to Create Two Children
 //     randnum = r.nextDouble();
 //     if (randnum < Parameters.xoverRate){
 //      Chromo.mateParents(parent1, parent2, member[parent1], member[parent2], child[i], child[i+1]);
 //     }
 //     else {
 //      Chromo.mateParents(parent1, member[parent1], child[i]);
 //      Chromo.mateParents(parent2, member[parent2], child[i+1]);
 //     }
 //    } // End Crossover
    
    //multiparent crossover mechanism
   
    {
     int[] parentsChosen = new int[Parameters.crossoverParents];
     FloatChromo[] parents = new FloatChromo[Parameters.crossoverParents];
     int tempParent; 
     
     for (int i = 0; i < child.length; i++) {
      if (r.nextDouble() < parmValues.xoverRate) {
       for (int j = 0; j < parentsChosen.length; j++) {
        parentsChosen[j] = -1;
       }
       for (int j = 0; j < parentsChosen.length; j++) {
        tempParent = Chromo.selectParent();
        for (int k = 0; k <= j; k++) {
         if (j==k)
          parentsChosen[k] = tempParent;
         else if (parentsChosen[k]==tempParent) {
          tempParent = Chromo.selectParent();
          k = 0;
         }
        }
       }
       for (int j = 0; j < parents.length; j++) {
        parents[j] = (FloatChromo)member[parentsChosen[j]];
       }

       child[i] = FloatChromo.mateParents(parents);
      }
      else 
       child[i] = member[Chromo.selectParent()];
     }
    }
    
    // Mutate Children
    for (int i=0; i<Parameters.popSize; i++){
     ((FloatChromo)child[i]).doMutation();
    }

    // Swap Children with Last Generation
    for (int i=0; i<Parameters.popSize; i++){
     Chromo.copyB2A(member[i], child[i]);
    }

   } //  Repeat the above loop for each generation

   Hwrite.left(bestOfRunR, 4, summaryOutput);
   Hwrite.right(bestOfRunG, 4, summaryOutput);

   problem.doPrintGenes(bestOfRunChromo, summaryOutput);

   System.out.println(R + "\t" + "B" + "\t"+ bestOfRunChromo.rawFitness);

         // Save the best runs fitness to our csv writer
         endBestStatsWriter.addDatum(0,bestOfRunChromo.rawFitness);
         summaryOutput.write("BF " + bestOfRunChromo.rawFitness);

         // Save when the first optimum was found if it was found
         if (Parameters.generations != firstOptimalGeneration)
            firstOptimumStatsWriter.addDatum(0,firstOptimalGeneration);
  summaryOutput.write("\nGEN " + firstOptimalGeneration + "\n");
  } //End of a Run

  Hwrite.left("B", 8, summaryOutput);

  problem.doPrintGenes(bestOverAllChromo, summaryOutput);

  // Output Fitness Statistics matrix
  summaryOutput.write("Gen                 AvgFit              BestFit \n");
  for (int i=0; i<Parameters.generations; i++){
   Hwrite.left(i, 15, summaryOutput);
   Hwrite.left(fitnessStats[0][i]/Parameters.numRuns, 20, 2, summaryOutput);
   Hwrite.left(fitnessStats[1][i]/Parameters.numRuns, 20, 2, summaryOutput);
   summaryOutput.write("\n");
  }

  summaryOutput.write("\n");
  summaryOutput.close();

      // Write our csv files out!
      avgBestFitnessWriter.close();
      avgAvgFitnessWriter.close();
      endBestStatsWriter.close();

  System.out.println();
  System.out.println("Start:  " + startTime);
  dateAndTime = Calendar.getInstance(); 
  Date endTime = dateAndTime.getTime();
  System.out.println("End  :  " + endTime);

 } // End of Main Class

}   // End of Search.Java ******************************************************

